package indexer;

public class QuickSort {
    private static int nElems;
    private static Integer[] data;

    public static Integer[] Sort(Integer[] datain){
    	data=new Integer[datain.length];
    	System.arraycopy(datain, 0, data, 0, datain.length);
    		
    	nElems=data.length;
        recQuickSort(0, nElems-1);
        Integer [] dataout=new Integer[data.length];
        System.arraycopy(data, 0, dataout, 0, data.length);
        return dataout;
    }
    
    private static void swap(int dex1, int dex2) {					
        Integer temp = data[dex1];
        data[dex1] = data[dex2];
        data[dex2] = temp;
    }
    
    private static int partitionIt(int left, int right, double pivot) {
        int leftPtr = left;									
        int rightPtr = right - 1;							
        
        while(true) {
            while(data[++leftPtr] < pivot)					
                ;
            while(data[--rightPtr] > pivot)					
                ;
            if(leftPtr >= rightPtr)							
                break;
            else											
                swap(leftPtr, rightPtr);
        }
        swap(leftPtr, right-1);								
        return leftPtr;										
    }
    
    private static Integer medianOf3(int left, int right) {
        int center = (left + right)/2;
        if(data[left] > data[center])						
            swap(left, center);
        if(data[left] > data[right])						
            swap(left, right);
        if(data[center] > data[right])						
            swap(center, right);
        swap(center, right-1);								
        return data[right-1];								
    }
    
    private static void recQuickSort(int left, int right) {
        int size = right - left + 1;
        if(size < 20) {
            int in, out;
            for(out=left+1; out<=right; out++) {
                Integer temp = data[out];
                in = out;
                while(in>left && data[in-1]>=temp) {
                    data[in] = data[in-1];
                    in--;
                }
                data[in] = temp;
            }
        }
        else {
            Integer median = medianOf3(left, right);
            int partition = partitionIt(left, right, median);
            recQuickSort(left, partition-1);
            recQuickSort(partition+1, right);
        }
    }
}
